package 树;

import javax.swing.*;
import java.util.*;

public class 二叉树前中后序遍历的实现<E> {
    public TreeNode<E> root;

    public void build() {
        //创建一个树
        TreeNode<Character> node = new TreeNode<>('A');
        TreeNode<Character> node1 = new TreeNode<>('B');
        TreeNode<Character> node2 = new TreeNode<>('C');
        TreeNode<Character> node3 = new TreeNode<>('D');
        TreeNode<Character> node4 = new TreeNode<>('E');
        TreeNode<Character> node5 = new TreeNode<>('F');
        TreeNode<Character> node6 = new TreeNode<>('G');
        TreeNode<Character> node7 = new TreeNode<>('H');
        //构造
        node.left = node1;
        node.right = node2;
        node1.left = node3;
        node1.right = node4;
        node4.left = node6;
        node4.right = node7;
        node2.right = node5;

        root = (TreeNode<E>) node;
    }

    /**
     * 方法功能：传入头节点先序遍历根左右遍历所有节点
     */
    public void  preOrder1(TreeNode<Character> root){
        //如果节点的值为空，直接返回，空节点
        if (root == null){
            return;
        }
        //创建一个队列辅助迭代
        Deque stack = new LinkedList();
        //将根节点放入栈中
        stack.offer(root);
        //开始遍历栈，为空则退出
        while (!stack.isEmpty()){
            TreeNode pop = (TreeNode) stack.pop();
            System.out.print(pop.val+" ");
            if (pop.right != null){
                stack.push(pop.right);
            }
            if (pop.left != null){
                stack.push(pop.left);
            }
        }
    }

    /**
     * 方法功能：传入头节点先序遍历根左右遍历所有节点
     */
    public void  preOrder(TreeNode<Character> root){
        //如果节点的值为空，直接返回，空节点
        if (root == null){
            return;
        }
        //g根左右，先打印根
        System.out.print(root.val + " ");
        //将打印左子树的任务交给具有该功能的方法
        preOrder(root.left);
        //将打印右子树的任务交给具有该功能的方法
        preOrder(root.right);
    }

    /**
     * 该方法具有按照中序遍历左根右顺序打印树的每个节点
     * @param root
     */
    public void midOrder1(TreeNode root){
        if (root == null) {
            return;
        }
        Deque<TreeNode> stack = new LinkedList();

        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()){

            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();
            System.out.print(cur.val+" ");
            cur = cur.right;
        }
    }

    /**
     * 该方法具有按照中序遍历左根右顺序打印树的每个节点
     * @param root
     */
    public void midOrder(TreeNode root){
        if (root == null) {
            return;
        }
        //先打印左链表
        midOrder(root.left);
        //打印根节点
        System.out.print(root.val+" ");
        //最后打印右子树节点
        midOrder(root.right);
    }

    /**
     * 该方法具有按照后序遍历左右根顺序打印树的每个节点
     * @param root
     */
    public void lastOrder(TreeNode root){

        if (root == null){
            return;
        }
        //先打印左子树
        midOrder(root.left);
        //在打印右子树
        midOrder(root.right);
        //最后打印根节点
        System.out.print(root.val+" ");
    }

    /**
     * 统计节点个数的方法
     * @param root
     * @return
     */
    public int getNodes(TreeNode root){
        //如果节点为空，返回0
        if (root == null){
            return 0;
        }
        //否则至少存在一个节点，1+后面左右子树的节点
        //左右子树的节点的个数我不知道，交给具有改功能的方法。
        return 1 + getNodes(root.left) + getNodes(root.right);

//        return root == null ? 0 : 1 + getNodes(root.left) + getNodes(root.right);
    }

    /**
     * 统计叶子节点个数的方法
     * @param root
     * @return
     */
    public int getLeafNodes(TreeNode root){
        //如果节点为空，返回0
        if (root == null){
            return 0;
        }
        //如果节点没有左孩子，同时没有右孩子，则是叶子节点，返回1
        if ((root.left == null) && (root.right == null)){
            return 1;
        }
        //走到这里，则至少说明，这颗树中存在2及以上的节点，
        // 左右子树中右几个叶子节点我不知道
        //将左右子树交给具有改功能的方法，来求他们右多少个叶子节点
        return getLeafNodes(root.left) + getLeafNodes(root.right);
    }

    /**
     * 给一个根节点和第k层，就可以求出第k层的节点的个数
     * @param root
     * @param k
     * @return
     */
    public int getKleafNodes(TreeNode root,int k){
        //如果节点为空，返回0
        if (root == null || k < 1){
            return 0;
        }
        //如果就是求第一层，返回1，第一层就只有一个节点
        if (k == 1){
            return 1;
        }
        //否则，k至少为2层，此时左右子树的叶子节点个数我不知道，将他交给具有该功能的方法替我求出
        return (getKleafNodes(root.left,k-1) + getKleafNodes(root.right,k-1));
    }

    /**
     * 给你一个根节点，你就可以求出树高的方法
     * @param root
     * @return
     */
    public int getHeight(TreeNode root){
        //如果树为空，则返回0
        if (root == null){
            return 0;
        }
        //走到这里说明，至少存在一个根节点，树高 = 1 + 左子树与右子树的最大值
        return 1 + Math.max(getHeight(root.left),getHeight(root.right));
    }

    /**
     * 给你一个根节点和一个值val，你就可以判断树中是否存在val
     * @param root
     * @param val
     * @return
     */
    public boolean contains(TreeNode<E> root,E val){
        //如果树为空，返回false
        if (root == null){
            return false;
        }
        //如果root就为这个值，则返回true
        if (root.val.equals(val)){
            return true;
        }
        //走到这里说明，树根不等于val，则在根节点的左右子树中查找
        //左右子树的是否包含我不知道，交给一个具有该功能的方法来实现
        return (contains(root.left,val) || contains(root.right,val));
    }

    /**
     * 二叉树的层序遍历
     * @param root
     */
    public void layerOrder(TreeNode<E> root){ ;
        if (root == null){
            return;
        }
        Queue queue = new LinkedList();
        queue.offer(root);

        while (!queue.isEmpty()){
            TreeNode node = (TreeNode) queue.poll();
            System.out.print(node.val+" ");
            if (node.left != null){
                queue.offer(node.left);
            }
            if (node.right != null){
                queue.offer(node.right);
            }
        }
    }
}



class TestTree{
    public static void main(String[] args) {
        二叉树前中后序遍历的实现 o = new 二叉树前中后序遍历的实现();
        o.build();
        System.out.print("前序遍历递归法：");
        o.preOrder(o.root);
        System.out.println();
        System.out.print("前序遍历迭代法：");
        o.preOrder1(o.root);
        System.out.println();
        System.out.print("中序递归遍历：");
        o.midOrder(o.root);
        System.out.println();
        System.out.print("中序遍历迭代：");
        o.preOrder1(o.root);
        System.out.println();
        System.out.print("后序遍历：");
        o.lastOrder(o.root);
        System.out.println();
        System.out.print("节点个数：");
        System.out.print(o.getNodes(o.root));
        System.out.println();
        System.out.print("叶子节点个数：");
        System.out.print(o.getLeafNodes(o.root));
        System.out.println();
        System.out.print("第K层叶子节点个数：");
        System.out.print(o.getKleafNodes(o.root,3));
        System.out.println();
        System.out.print("树的高度：");
        System.out.print(o.getHeight(o.root));
        System.out.println();
        System.out.print("树中是否包含D：");
        System.out.print(o.contains(o.root,'D'));
        System.out.println();
        System.out.print("树中是否包含L：");
        System.out.print(o.contains(o.root,'L'));
        System.out.println();
        System.out.print("二叉树的层序遍历：");
        o.layerOrder(o.root);
        System.out.println();
    }
}
